package com.study.lihan.letcode;

public class TestDaynamicPlan {
    static  int[][] grid = {{1,2,3},{4,5,6}};

    public static void main(String[] args) {
       int result = minPathSum(grid);
        System.out.println("结果是："+ result);
    }

     static int forgeJump(int n){
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1]= 1;
        dp[2] =2;

        if(n <0) return -1;
        if(n==0) return dp[0];
        if(n==1) return dp[1];
        if(n==2) return  dp[2];

        for(int i = 3; i<=n ; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }

        return  dp[n];
     }


   static  public int uniquePaths(int m, int n) {
       if(m<1 || n<1)return  0;

    int [][] dp = new int[m][n];

    for(int i= 0; i< m; i++){
        dp[i][0] = 1;
    }
    for(int i=0; i<n; i++){
        dp[0][i] = 1;
    }

    for(int i =1; i< m; i++){
        for(int j=1; j<n; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
    }


    public static  int minPathSum(int[][] grid) {
        int width = grid[0].length;
        int height = grid.length;
        if(grid==null) return 0;
        int  dp [][] = new int[height][width];

       dp[0][0]= grid[0][0];
        for(int i = 1; i<width; i++){
            dp[0][i]= grid[0][i] + dp[0][i-1];
        }
        for(int i=1; i<height; i++){
            dp[i][0] = grid[i][0] + dp[i-1][0];
        }

        for(int i =1; i<height; i++){
            for(int j =1; j<width; j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }

        return dp[height-1][width-1];
    }
}
